//给定一个二叉树，检查它是否是镜像对称的。 
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 
// 👍 1126 👎 0

package com.everyday.algorithm.changyf.leetcode.editor.cn;
public class SymmetricTree {
    public static void main(String[] args) {
        Solution solution = new SymmetricTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : traverse(root.left, root.right);
    }
    public boolean traverse(TreeNode p, TreeNode q){
        //都不为null时，对比值
        if (p != null && q != null){
            //值不相等返回false，否则对比子节点
            if (p.val != q.val){
                return false;
            }
        }else if (p == null && q == null){//都为null时，返回true
            return true;
        }else {//一个为null时，返回false
            return false;
        }
        return traverse(p.left,q.right) && traverse(p.right,q.left);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}